package algorithms

import "cmp"

// 这里的快排也叫原地快排，因为没有产生新的内存
func QuickSort[T cmp.Ordered](collection []T) {
	if len(collection) <= 1 {
		return
	}

	current := 0
	i := 1
	j := len(collection) - 1
	for i < j {
		for ; i < j; j-- {
			if collection[j] < collection[current] {
				// 对 j 的循环结束条件是 j = current
				break
			}
		}
		for ; i < j; i++ {
			if collection[i] > collection[current] {
				// 对 i 的循环结束条件是 i = current
				break
			}
		}
		// 如果 i j 没有相遇 那么互换位置
		if i < j {
			collection[i], collection[j] = collection[j], collection[i]
		}
	}

	// i 与 j 相遇后, 如果 i < current , 则交换 i、current
	if collection[i] < collection[current] {
		collection[current], collection[i] = collection[i], collection[current]
		current = i
	}

	// 拆分子切片进行分治
	if current > 0 {
		QuickSort(collection[:current])
	}

	if current < len(collection)-1 {
		QuickSort(collection[current+1:])
	}
}
